#include <iostream>
#include <vector>

using namespace std;

int main() {
    int n;
    vector<int> solu;
    solu.push_back(0);
    solu.push_back(1);
    while (cin >> n) {
        if (n == -1)
            break;
        while (static_cast<int>(solu.size()) <= n)
            solu.push_back((solu[solu.size() - 2] + solu[solu.size() - 1]) % 10000);

        cout << solu[n] << endl;
    }
    return 0;
}
